Handwriting recognition systems allow users to input handwritten data into a computer. The user writes data on an electronic tablet with a special pen, and as the user moves the pen across the tablet, the tablet displays to the user lines which in appearance are much like handwritten lines on a paper tablet. A computer program handwriting recognizer, given data as a set of strokes, attempts to recognize the set of strokes as characters in an alphabet. The recognizer recognizes by comparing the set of strokes forming a symbol with stored character models.
Very often, because of the great variation in the way people write, the recognizer is not able to decide unambiguously the character a particular set of strokes was intended to denote. For example, if a user writes the word "cat," the recognizer may be able to deduce that there are three symbols written but may not be able to unambiguously recognize all of them. It may, for example, think that the middle symbol is either the letter "a" or "u." To convey this ambiguity, the recognizer produces a set of one or more alternatives for each symbol. The alternatives are arranged within a set from an alternative having the highest probability of corresponding to the written symbol to an alternative having the lowest probability of corresponding to the written symbol. The recognizer determines the relative probability based on how closely the set of strokes forming the symbol approximate the stored character models. Typically, each alternative is a single character but multiple character combinations are also possible. For example, if the symbols "c" and "l" are written too closely together they approximate the character "d." Therefore, the recognizer may produce one alternative being the character "d" and another alternative being a combination of the characters "c" and "l."
Once the recognizer produces a set of alternatives for each written symbol, some processing must be performed to determine which alternative from each set should be used to form a word. One processing method enumerates strings of different combinations of the alternatives and looks up each string in a dictionary.
Various methods could be used to enumerate strings. Enumeration may proceed by producing every possible combination of alternatives in random order. While this method may be accurate to determine the string that the user intended, it is very time-consuming to process, since an attempt must be made to find in the dictionary corresponding words for each string. The recognizer may produce 5-10 alternatives for each symbol. For longer words, literally millions of possible strings may be enumerated. Multiplying the time it takes to enumerate each string by the time it takes to look up each string in the dictionary results in unacceptably long processing times.